import collections


class Solution(object):
    def maxSum(self, nums1, nums2):
        base = 10 ** 9 + 7
        m1 = len(nums1)
        m2 = len(nums2)
        DP1 = [0] * m1
        DP2 = [0] * m2
        index1 = 0
        index2 = 0
        while index1 < m1 and index2 < m2:
            if nums1[index1] == nums2[index2]:
                if index1 == 0:
                    if index2 == 0:
                        DP1[index1], DP2[index2] = nums1[index1], nums1[index1]
                    else:
                        DP1[index1], DP2[index2] = DP2[index2 - 1] + nums2[index2], max(
                            nums1[index1], DP2[index2 - 1] + nums2[index2])
                else:
                    if index2 == 0:
                        DP1[index1], DP2[index2] = max(DP1[index1 - 1] + nums1[index1], nums1[index1]), \
                                                   DP1[index1 - 1] + nums1[index1]
                    else:
                        DP1[index1], DP2[index2] = max(DP1[index1 - 1] + nums1[index1],
                                                       DP2[index2 - 1] + nums2[index2]), max(
                            DP2[index2 - 1] + nums2[index2], DP1[index1 - 1] + nums2[index2])
                index1 += 1
                index2 += 1
            else:
                if index1 == 0:
                    if index2 == 0:
                        DP1[index1], DP2[index2] = nums1[index1], nums2[index2]
                    else:
                        DP1[index1], DP2[index2] = nums1[index1], DP2[index2 - 1] + nums2[index2]
                else:
                    if index2 == 0:
                        DP1[index1], DP2[index2] = nums1[index1] + DP1[index1 - 1], nums2[index2]
                    else:
                        DP1[index1], DP2[index2] = nums1[index1] + DP1[index1 - 1], DP2[index2 - 1] + nums2[index2]
                if nums1[index1] < nums2[index2]:
                    index1 += 1
                else:
                    index2 += 1
        while index1 < m1:
            if index1 == 0:
                DP1[index1] = nums1[index1]
            else:
                DP1[index1] = DP1[index1 - 1] + nums1[index1]
            index1 += 1
        while index2 < m2:
            if index2 == 0:
                DP2[index2] = nums2[index2]
            else:
                DP2[index2] = DP2[index2 - 1] + nums2[index2]
            index2 += 1
        return max(DP1[-1], DP2[-1]) % base


data = Solution()
nums1 = [2, 4, 5, 8, 10]
nums2 = [4, 6, 8, 9]
print(data.maxSum(nums1, nums2))
